package Top_Interview_Questions_Review._011Heap;

import java.util.Arrays;
import java.util.PriorityQueue;

/**
 * @Author: 吕庆龙
 * @Date: 2020/3/2 12:14
 * <p>
 * 功能描述:
 */
public class _0215 {

    public static void main(String[] args) {
        _0215 test = new _0215();
        int[] nums = {3,2,1,5,6,4};

        int kmax = test.findKthLargest1(nums, 2);
        System.out.println(kmax);
    }

    /*------------------------------------------堆------------------------------------------*/

    /**
     * https://leetcode-cn.com/problems/kth-largest-element-in-an-array/solution/shu-zu-zhong-de-di-kge-zui-da-yuan-su-by-leetcode/
     *
     */
    public int findKthLargest1(int[] nums, int k) {
        // init heap 'the smallest element first'
        PriorityQueue<Integer> heap =
                new PriorityQueue<Integer>((n1, n2) -> n1 - n2);

        // keep k largest elements in the heap
        for (int n: nums) {
            heap.add(n);
            if (heap.size() > k)
                heap.poll();
        }

        // output
        return heap.poll();
    }


    /*--------------------------------------------------------------------------------------*/


    /*----------------------------------------自己写的---------------------------------------*/

    /**
     * Java的Arrays.sort用的是归并排序,时间复杂度为O(nlogn)
     */
    public int findKthLargest(int[] nums, int k) {
        Arrays.sort(nums);
        return nums[nums.length - k];
    }

    /*--------------------------------------------------------------------------------------*/
}
